package org.labuladong.动态规划算法.一维DP;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * @Auther: qingle
 * @Date: 2024/10/26-14:48
 * @Description:
 *
 * 你是⼀个专业的⼩偷，计划偷窃沿街的房屋。这个地⽅所有的房屋都围成⼀
 * 圈，这意味着第⼀个房屋和最后⼀个房屋是紧挨着的。
 * 每间房内都藏有⼀定的现⾦，影响你偷窃的唯⼀制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同⼀晚上被⼩偷闯⼊，系统会⾃动报警。
 * 给定⼀个代表每个房屋存放⾦额的⾮负整数数组，计算你不触动警报装置的情况下，⼀夜之内能够偷窃到的最⾼⾦额。
 * 示例 1：
 * 输⼊：[1,2,3,1]
 * 输出：4
 * 解释：偷窃 1 号房屋（⾦额 = 1)，然后偷窃 3 号房屋（⾦额 = 3)。
 *  偷窃到的最⾼⾦额 = 1 + 3 = 4。
 *
 * @version: 1.0
 */


public class LC_213打家劫舍III_DP {

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode() {}
		TreeNode(int val) { this.val = val; }
		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

	class Solution {
		Map<TreeNode, Integer> memo = new HashMap<>();

		public int rob(TreeNode root) {
			if (root == null) return 0;
			// 利用备忘录消除重叠子问题
			if (memo.containsKey(root)) {
				return memo.get(root);
			}
			// 抢，然后去下下家
			int do_it = root.val;
			if (root.left != null) {
				do_it += rob(root.left.left) + rob(root.left.right);
			}
			if (root.right != null) {
				do_it += rob(root.right.left) + rob(root.right.right);
			}
			// 不抢，然后去下家
			int not_do = rob(root.left) + rob(root.right);
			// 取两种情况的最大值
			int res = Math.max(do_it, not_do);
			// 将结果存入备忘录
			memo.put(root, res);
			return res;
		}
	}

	public static void main(String[] args)
	{
		LC_213打家劫舍III_DP lc = new LC_213打家劫舍III_DP();
		TreeNode root = lc.new TreeNode(3);
		root.left = lc.new TreeNode(4);
		root.right = lc.new TreeNode(5);
		root.left.left = lc.new TreeNode(1);
		root.left.right = lc.new TreeNode(3);
		root.right.right = lc.new TreeNode(1);
	}
}
